#[derive(Debug, Clone, Copy, PartialEq)]
enum BinaryHeapType {
    BINARY_HEAP_TYPE_MIN,
    BINARY_HEAP_TYPE_MAX,
}
type BinaryHeapValue = *mut std::ffi::c_void;
type BinaryHeapCompareFunc = fn(value1: BinaryHeapValue, value2: BinaryHeapValue) -> i32;
struct BinaryHeap {
    heap_type: BinaryHeapType,
    values: *mut BinaryHeapValue,
    num_values: u32,
    alloced_size: u32,
    compare_func: BinaryHeapCompareFunc,
}
const BINARY_HEAP_NULL: *mut std::ffi::c_void = std::ptr::null_mut();
fn binary_heap_cmp(heap: *const BinaryHeap, data1: BinaryHeapValue, data2: BinaryHeapValue) -> i32 {
    unsafe {
        if (*heap).heap_type == BinaryHeapType::BINARY_HEAP_TYPE_MIN {
            ((*heap).compare_func)(data1, data2)
        } else {
            -((*heap).compare_func)(data1, data2)
        }
    }
}
fn binary_heap_new(
    heap_type: BinaryHeapType,
    compare_func: BinaryHeapCompareFunc,
) -> *mut BinaryHeap {
    unsafe {
        let heap = malloc(std::mem::size_of::<BinaryHeap>()) as *mut BinaryHeap;
        if heap.is_null() {
            return ptr::null_mut();
        }
        (*heap).heap_type = heap_type;
        (*heap).num_values = 0;
        (*heap).compare_func = compare_func;
        (*heap).alloced_size = 16;
        (*heap).values =
            malloc(std::mem::size_of::<BinaryHeapValue>() * (*heap).alloced_size as usize)
                as *mut BinaryHeapValue;
        if (*heap).values.is_null() {
            free(heap as *mut c_void);
            return ptr::null_mut();
        }
        heap
    }
}
fn binary_heap_free(heap: *mut BinaryHeap) {
    unsafe {
        if !(*heap).values.is_null() {
            libc::free((*heap).values);
        }
        libc::free(heap as *mut libc::c_void);
    }
}
fn binary_heap_insert(heap: *mut BinaryHeap, value: BinaryHeapValue) -> i32 {
    unsafe {
        let mut new_values: *mut BinaryHeapValue;
        let mut index: u32;
        let mut new_size: u32;
        let mut parent: u32;
        if (*heap).num_values >= (*heap).alloced_size {
            new_size = (*heap).alloced_size * 2;
            new_values = libc::realloc(
                (*heap).values as *mut libc::c_void,
                std::mem::size_of::<BinaryHeapValue>() * new_size as usize,
            ) as *mut BinaryHeapValue;
            if new_values.is_null() {
                return 0;
            }
            (*heap).alloced_size = new_size;
            (*heap).values = new_values;
        }
        index = (*heap).num_values;
        (*heap).num_values += 1;
        while index > 0 {
            parent = (index - 1) / 2;
            if binary_heap_cmp(heap, (*heap).values.offset(parent as isize), value) < 0 {
                break;
            } else {
                *(*heap).values.offset(index as isize) = *(*heap).values.offset(parent as isize);
                index = parent;
            }
        }
        *(*heap).values.offset(index as isize) = value;
        1
    }
}
fn binary_heap_pop(heap: &mut BinaryHeap) -> BinaryHeapValue {
    let mut result: BinaryHeapValue;
    let mut new_value: BinaryHeapValue;
    let mut index: usize;
    let mut next_index: usize;
    let mut child1: usize;
    let mut child2: usize;
    if heap.num_values == 0 {
        return BINARY_HEAP_NULL;
    }
    result = heap.values[0];
    new_value = heap.values[heap.num_values as usize - 1];
    heap.num_values -= 1;
    index = 0;
    loop {
        child1 = index * 2 + 1;
        child2 = index * 2 + 2;
        if child1 < heap.num_values as usize
            && binary_heap_cmp(heap, new_value, heap.values[child1]) > 0
        {
            if child2 < heap.num_values as usize
                && binary_heap_cmp(heap, heap.values[child1], heap.values[child2]) > 0
            {
                next_index = child2;
            } else {
                next_index = child1;
            }
        } else if child2 < heap.num_values as usize
            && binary_heap_cmp(heap, new_value, heap.values[child2]) > 0
        {
            next_index = child2;
        } else {
            heap.values[index] = new_value;
            break;
        }
        heap.values[index] = heap.values[next_index];
        index = next_index;
    }
    result
}
fn binary_heap_num_entries(heap: &BinaryHeap) -> u32 {
    heap.num_values
}

